The Vandermonde decomposition of Toeplitz matrices, discovered byCarath\'{e}odory and Fej\'{e}r in the 1910s and rediscovered by Pisarenko inthe 1970s, forms the basis of modern subspace methods for 1D frequencyestimation. Many related numerical tools have also been developed formultidimensional (MD), especially 2D, frequency estimation; however, afundamental question has remained unresolved as to whether an analog of theVandermonde decomposition holds for multilevel Toeplitz matrices in the MDcase. In this paper, an affirmative answer to this question and a constructivemethod for finding the decomposition are provided when the matrix rank is lowerthan the dimension of each Toeplitz block. A numerical method for searching fora decomposition is also proposed when the matrix rank is higher. The newresults are applied to studying MD frequency estimation within the recentsuper-resolution framework. A precise formulation of the atomic $\ell_0$ normis derived using the Vandermonde decomposition. Practical algorithms forfrequency estimation are proposed based on relaxation techniques. Extensivenumerical simulations are provided to demonstrate the effectiveness of thesealgorithms compared to the existing atomic norm and subspace methods.
展开▼
